package com.demo.java.OD601_650.OD608;

import java.util.*;


/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【批量处理任务(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146591580
 */
public class OdMain {
    public static void main(String[] args) {
        // 示例任务数组 {start, end, duration}
        int[][] tasks = {{2,3,1}, {5,5,1}, {5,6,2}};

        // 调用处理任务的方法并输出结果
        System.out.println(processTasks(tasks));
    }

    public static int processTasks(int[][] tasks) {
        // 按照任务的结束时间进行排序
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);

        // 用一个列表栈来处理任务的区间
        ArrayList<int[]> st = new ArrayList<int[]>();
        // 初始化栈底元素 (-2, -2, 0)，表示无效区间
        st.add(new int[]{-2, -2, 0});

        // 遍历所有任务
        for (int[] t : tasks) {
            int start = t[0], end = t[1], d = t[2];
            // 获取当前任务开始时间之前的最新任务区间
            int[] e = st.get(lowerBound(st, start) - 1);
            // 去除已经运行的时间段
            d -= st.get(st.size() - 1)[2] - e[2];

            // 如果任务的时间已经用完，跳过该任务
            if (start <= e[1]) {
                d -= e[1] - start + 1;
            }
            if (d <= 0) continue; // 剩余时间为零，跳过

            // 尝试合并区间
            while (end - st.get(st.size() - 1)[1] <= d) {
                e = st.remove(st.size() - 1);
                d += e[1] - e[0] + 1; // 合并区间时累加已用时间
            }
            // 添加新的任务区间
            st.add(new int[]{end - d + 1, end, st.get(st.size() - 1)[2] + d});
        }
        // 返回最后任务区间的总时间
        return st.get(st.size() - 1)[2];
    }

    // 使用二分查找来获取比目标时间更早的区间的位置
    private static int lowerBound(List<int[]> st, int target) {
        int left = -1, right = st.size();
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (st.get(mid)[0] < target)
                left = mid; // 缩小搜索区间
            else
                right = mid; // 缩小搜索区间
        }
        return right; // 返回合适的位置
    }
}